package everyday;

import common.ListNode;

/**
 * @author zhangmin
 * @create 2022-04-28 22:10
 *
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 *
 * 思路：
 * 使用归并排序，每次划分出长度为1，2，3.。的子链，然后将相邻的子链进行merge
 */
public class sortList148 {
    public ListNode merge(ListNode list1,ListNode list2){
        if (list1==null) return list2;
        if (list2==null) return list1;
        ListNode head=new ListNode(-1),p=head;
        while (list1!=null||list2!=null){
            if (list1==null){
                p.next=list2;
                return head.next;
            }else if (list2==null){
                p.next=list1;
                return head.next;
            }else if (list1.val<=list2.val){
                p.next=list1;
                list1=list1.next;
            }else {
                p.next=list2;
                list2=list2.next;
            }
            p=p.next;
        }
        return head.next;
    }

    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null) return head;
        int len=0;
        ListNode p=head,newhead=new ListNode(-1,head);
        //计算出链表的长度
        while (p!=null){
            p=p.next;
            len++;
        }
        for (int i = 1; i < len; i<<=1) {
            ListNode pre=newhead,cur=newhead.next;
            while (cur!=null){
                //记录第一个链表的头节点
                ListNode head1=cur;
                for (int j = 1; j < i&&cur.next!=null; j++) {
                    cur=cur.next;
                }
                //此时是head1的最后一个节点
                ListNode head2=cur.next;
                cur.next=null; //将第一个链表断开
                cur=head2;
                for (int j = 1; j < i&&cur!=null&&cur.next!=null; j++) {
                    cur=cur.next;
                }
                //next记录接下来还没有划分到的链表
                ListNode next=null;
                if (cur!=null){
                    next=cur.next;
                    cur.next=null;
                }
                ListNode merge = merge(head1, head2);
                pre.next=merge;
                while (pre.next!=null){
                    pre=pre.next;
                }
                cur=next;
            }
        }
        return newhead.next;
    }
}
